int Max(int x, int y) {
    return (x > y) ? x : y;
}

int WeightedActivitySelection(Activities a, int n) {
    /* n个活动按照 a[i].finish 的非递减序存放 */
    int *w, i, k;

    w = (int *)malloc(sizeof(int) * (n + 1));
    w[0] = 0;
    for (i = 1; i <= n; i++) {
        for (k = i - 1; k > 0;
                k--) { /* 找到与i不冲突的最后一个结束的俱乐部的序号 */
            if (a[k].finish <= a[i].start) {
                break;
            }
        }
        /* 取批准与不批准两者的最大值 */
        w[i] = Max(w[i - 1], w[k] + a[i].weight);
    }
    return w[n];
}